图解算法1 - 简单查找法、二分法、大O表示法

简单查找法

简单查找更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99，你得猜99次才能猜到

二分查找法

一般而言，对于包含n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步

运行时间

线性时间

简单查找逐个地检查数字，如果列表包含100个数字，最多需要猜100次。如果列表包含40亿个数字，最多需要猜40亿次。换言之，最多需要猜测的次数与列表长度相同，这被称为线性时间（linear time）

对数时间

二分查找则不同。如果列表包含100个元素，最多要猜7次；如果列表包含40亿个数字，最多
需猜32次。二分查找的运行时间为对数时间（或log时间）

大O表示法

时间增速

二分查找和简单查找的运行时间的增速不同，也就是说，随着元素数量的增加，二分查找需要的额外时间并不多，而简单查找需要的额外时间却很多。因此，随着列表的增长，二分查找的速度比简单查找快得多。

大O的定义

假设列表包含n个元素。简单查找需要检查每个元素，因此需要执行n次操作。使用大O表示法，这个运行时间为O(n)【大O表示法指的并非以秒为单位的速度。大O表示法让你能够比较操作数，它指出了算法运行时间的增速】

再来看一个例子。为检查长度为n的列表，二分查找需要执行log n次操作。使用大O表示法表示为 O(log n)【指出了算法需要执行的操作数】

大O表示最糟情况

注意：大 O 表示法指出了最糟情况下的运行时间。假设你使用简单查找在电话簿中找人。你知道，简单查找的运行时间为O(n)，这意味着在最糟情况下，必须查看电话簿中的每个条目。如果要查找的是Adit——电话簿中的第一个人，一次就能找到，无需查看每个条目。考虑到一次就找到了Adit，请问这种算法的运行时间是O(n)还是O(1)呢？简单查找的运行时间总是为O(n)。查找Adit时，一次就找到了，这是最佳的情形，但大O表示法说的是最糟的情形。因此，你可以说，在最糟情况下，必须查看电话簿中的每个条目，对应的运行时间为O(n)

常见的大O运行时间

从快到慢排序

O(log n)，也叫对数时间，这样的算法包括二分查找。
O(n)，也叫线性时间，这样的算法包括简单查找。
O(n * log n)，这样的算法包括第4章将介绍的快速排序——一种速度较快的排序算法。
O(n2)，这样的算法包括第2章将介绍的选择排序——一种速度较慢的排序算法。
O(n!)，这样的算法包括接下来将介绍的旅行商问题的解决方案——一种非常慢的算法。

O(n!)的例子【旅行商问题】

有一位旅行商，他需要前往5个城市。同时要确保旅程最短。为此，可考虑前往这些城市的各种可能顺序。对于每种顺序，他都计算总旅程，再挑选出旅程最短的路线。 5个城市有120种不同的排列方式。因此，在涉及5个城市时，解决这个问题需要执行120次操作。涉及6个城市时，需要执行720次操作（有720种不同的排列方式）。涉及7个城市时，需要执行5040次操作！

小结

算法的速度指的并非时间，而是操作数的增速。
谈论算法的速度时，我们说的是随着输入的增加，其运行时间将以什么样的速度增加。
算法的运行时间用大O表示法表示。
O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快得越多。